package 力扣._295_数据流的中位数;

import java.util.*;

class MedianFinder {
    // 使用 最大堆 存储较小的一半数据
    // 使用 最小堆 存储较大的一半数据
    // 这样中位数就是两个堆顶元素的平均值，添加元素和访问中位数时也不会破坏对的结构
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    public MedianFinder() {

    }

    public void addNum(int num) {
        maxHeap.add(num);

        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.add(maxHeap.poll());
        }

    }

    public double findMedian() {
        System.out.println(maxHeap.peek());
        System.out.println(minHeap.peek());
        if(maxHeap.size() == minHeap.size())
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        else
            return maxHeap.peek();
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */